AtCoder M-SOLUTIONS プロコンオープン 2020 D - Road to Millionaire (400点)

https://gyazo.com/59016f90647e8bfa115eaa9daa7d18a7

考察履歴

入力例が最適でない

株の売買は全て、全買、全売で良さそう

極大、極小を抽出して、上がる見込みがあるなら株を買、下がる前に売れれば良い

二日間の株価変動は、上昇、不変、下降の３パターン

この３パターンによって処理を変えればいけるのではないか

傾きを抽出してやるのが答えへの一歩ではないか

実装したが、2TCでWA。。。

方針誤り。

結果的に考察の道が誤っていたが、コンテスト中は傾きのパターンのみで考え続けていた。

上昇、不変、下降の３パターン * 上昇、不変、下降の３パターンの9パターンとか

上昇、不変、下降の３パターンの図をたくさん書いて考えるとか

この２つは本質的に同じ考察であるので、線をたくさん書いても仕方がない！

問題文を見直すことはしていたので、見落としはなかった

10分以上悩んだら一度、方針を考える方法を考えるべき

いろいろな考え方がある

解説では、貪欲法と動的計画法での解説がある

貪欲法

どのような株も、１日で売って良い

というルールだけで良い

Twitterで目からうろこな解説があった

https://gyazo.com/ad5a45c62d4bfa36e877cc23de13009e

ランレングス圧縮！！

ランレングス圧縮してしまえば一気に単純化できる

数字に対してランレングス圧縮！なるほど！面白い！

これによって不変の場合を削除できて、問題が簡単になる

こういう考え方大切だと思う

https://gyazo.com/7919c84dc9e78dd13cd8c3109ff21892

code:rust

use std::io::*;

use std::str::FromStr;

fn read<T: FromStr>() -> T {

let stdin = stdin();

let stdin = stdin.lock();

let token: String = stdin

.bytes()

.map(|c| c.expect("failed to read char") as char)

.skip_while(|c| c.is_whitespace())

.take_while(|c| !c.is_whitespace())

.collect();

token.parse().ok().expect("failed to parse token")

}

fn main() {

let n:usize = read();

let a:Vec<u64> = (0..n).map(|_| read()).collect();

let mut money = 1000;

for i in 0..n-1{

}

}

println!("{}",money);

}